﻿/*
F 冬奥村网络布线方案
分数 30
作者 朱允刚
单位 吉林大学
冬奥会的奥运村是各国运动员在冬奥会期间的住宿公寓，冬奥会期间需要保证奥运村网络畅通，以使运动员都能正常上网。

假定奥运村有n个房间，编号为0…n−1，每个房间都需要网络连接。房间 i 有网络，当且仅当满足如下2个条件之一：

（1）房间 i 安装了路由器（成本为 r
i
​
 >0）

（2）房间 i 和房间 j 有网线连接且房间 j 有网络（在房间 i 和房间 j 之间布置网线的成本为 f
ij
​
 >0）

假定你是奥组委的网络工程师，请编写程序为奥组委设计一个网络布线方案（哪些房间安装路由器，哪些房间之间布置网线），使得所有房间都有网络，且总成本最小。

例如下图包含7个房间和10个可能的连接，安装路由器的成本为括号内数字，房间之间布置网线的成本为边的权值。其解决方案为右下图，即在房间1和4安装路由器，并进行图中的网线布置。总成本为120。

img.png

输入格式:
输入第一行为两个正整数n和e；n为房间数，不超过600；e为可能的连接数，不超过2×10
5
 。接下来一行为n个空格间隔的正整数，第i个整数(i≥0)表示在房间i安装路由器的成本。接下来e行，每行为3个非负整数i、j、f，表示在房间i和房间j之间布置网线的成本为f。

输出格式:
输出为一个整数，表示最优网络布线方案的成本。

输入样例:
7 10
60 10 35 55 40 70 70
0 1 20
0 4 75
0 3 45
1 3 50
1 2 15
2 6 5
5 6 45
4 5 5
3 5 25
3 6 65

输出样例:
120

提示:
可引入一个虚拟顶点，将该顶点与其他所有顶点用边相连，边权等于那些顶点的权值。进而形成一个新图，对新图求最小支撑树。注意本题顶点编号从0开始。
image.png
image.png

代码长度限制
16 KB
时间限制
60 ms
内存限制
64 MB
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int u, v, weight;
};

bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

int findParent(int vertex, vector<int>& parent) {
    if (parent[vertex] == -1) {
        return vertex;
    }
    else {
        return findParent(parent[vertex], parent);
    }
}

void unionVertices(int a, int b, vector<int>& parent) {
    int rootA = findParent(a, parent);
    int rootB = findParent(b, parent);
    parent[rootA] = rootB;
}

int main() {
    int n, e;
    cin >> n >> e;

    vector<int> routerCost(n);
    vector<Edge> edges(e);

    for (int i = 0; i < n; ++i) {
        cin >> routerCost[i];
    }

    for (int i = 0; i < e; ++i) {
        int u, v, f;
        cin >> u >> v >> f;
        edges[i] = { u, v, f };
    }

    sort(edges.begin(), edges.end(), compareEdges);

    vector<int> parent(n, -1);
    int totalCost = 0;

    for (int i = 0; i < e; ++i) {
        int u = edges[i].u;
        int v = edges[i].v;
        int weight = edges[i].weight;

        int rootU = findParent(u, parent);
        int rootV = findParent(v, parent);

        if (rootU != rootV) {
            if (routerCost[rootU] < routerCost[rootV]) {
                totalCost += routerCost[rootU] + weight;
                unionVertices(rootU, rootV, parent);
            }
            else {
                totalCost += routerCost[rootV] + weight;
                unionVertices(rootV, rootU, parent);
            }
        }
    }

    cout << totalCost << endl;

    return 0;
}


/*
这个程序使用Kruskal算法来找到最小生成树，保证所有房间都有网络的同时，总成本最小。
*/